<?php

/**
 * 二分查找(非递归版)
 */
function binarySearch($arr,$low,$top,$value)
{
    while($low<$top)
    {
        $mid = floor(($low+$top)/2);
        if ($arr[$mid] == $value)
        {
            return $mid;
        }
        elseif($arr[$mid]<$value)
        {
            $low = $mid+1;
        }
        else
        {
            $top = $mid-1;
        }
    }
    
    return -1;
}

$arr = [1,2,3,5,7,9,10,13,15,19,22];
$index = binarySearch($arr,0,count($arr),10);

var_dump($index);

/*
 * 递归版
 */
function binarySearchRecursive(&$arr,$low,$top,$value)
{
    if ($low<$top)
    {
        $mid = floor(($low+$top)/2);
        if ($arr[$mid] == $value)
        {
            return $mid;
        }
        elseif($arr[$mid]>$value)
        {
            return binarySearchRecursive($arr,0,$mid-1,$value);
        }
        else
        {
            return binarySearchRecursive($arr,$mid+1,$top,$value);
        }
    }
}
$arr = [1,2,3,5,7,9,10,13,15,19,22];
$index = binarySearchRecursive($arr,0,count($arr),10);
var_dump($index);
